﻿#include <iostream>
#include "../Util/util.h"

static int getWaterKingNumber(const int* numbers, const size_t numberCount)
{
	int candidate = 0;
	int hp = 0;
	int cur;
	for (int i = 0; i < numberCount; i++)
	{
		cur = numbers[i];
		if (hp == 0)
		{
			candidate = cur;
			hp = 1;
		}
		else if (candidate == cur)
		{
			++hp;
		}
		else
		{
			--hp;
		}
	}

	int candidateCount = 0;
	for (int i = 0; i < numberCount; i++)
	{
		cur = numbers[i];
		if (cur == candidate)
		{
			++candidateCount;
		}
	}

	if (candidateCount > numberCount / 2)
	{
		return candidate;
	}

	return -1;
}

/**
 * 超级水王
 * 给一组数字arr，长度是N，请找出这组数字中出现次数超过数字总数一半的数字。如果没有，返回-1
 * 要求：时间复杂度:O(N), 空间复杂度:O(1)
 * 
 * 思路：
 * 设arr=[3,1,2,3,3,4,3,5,3], 设置一个候选变量candidate，设置一个hp=0。
 * candidate在hp是0的时候没有意义。
 * 
 * step1:
 * [3,1,3,3,3,4,3,2,5,3]
 *  ↑
 * candidate=3, hp=1. 在hp=0的情况下，直接将当前index指向的数字设置为候选，hp+1
 * 
 * step2:
 * [3,1,3,3,3,4,3,2,5,3]
 *    ↑
 * candidate≠1, hp-1=0. index指向的数字不等于候选，则hp扣1变成0，candidate无效，继续下一个
 * 
 * step3:
 * [3,1,3,3,3,4,3,2,5,3]
 *      ↑
 * candidate=3， hp=1. 在hp==0的情况下，直接将当前index指向的数字设置为候选，hp+1
 * 
 * step4:
 * [3,1,3,3,3,4,3,2,5,3]
 *        ↑
 * candidate==3, hp+1=2. index指向的数字等于候选，则hp加1变成2，继续下一个
 * 
 * step5:
 * [3,1,3,3,3,4,3,2,5,3]
 *          ↑
 * candidate==3, hp+1=3
 * 
 * step6:
 * [3,1,3,3,3,4,3,2,5,3]
 *            ↑
 * candidate≠4，hp-1=2. index指向的数字不等于候选，则hp扣1变成2，继续下一个
 * 
 * step7:
 * [3,1,3,3,3,4,3,2,5,3]
 *              ↑
 * candidate==3, hp+1=3. 
 * 
 * step8:
 * [3,1,3,3,3,4,3,2,5,3]
 *                ↑
 * candidate≠2, hp-1=2. 
 * 
 * step9:
 * [3,1,3,3,3,4,3,2,5,3]
 *                  ↑
 * candidate≠5, hp-1=1. 
 * 
 * step10:
 * [3,1,3,3,3,4,3,2,5,3]
 *                    ↑
 * candidate==3, hp+1=2. 
 * 
 * 最终得到的candidate是3，则3可能是最终解，但是需要从头遍历一遍arr，数一下3的个数，3的个数满足大于数字总数量的一半，才能确定是最终解。
 */
int main_superWaterKing()
{
	int* numbers = nullptr;
	size_t numberCount = 10;
	generateSomeRandomNumbers(1, 4, &numbers, numberCount, false);

	printf("random numbers:\n");
	for (int i = 0; i < numberCount; i++)
	{
		printf("numbers[%d]=%d\n", i, numbers[i]);
	}

	int res = getWaterKingNumber(numbers, numberCount);
	printf("water king:%d\n", res);

	free(numbers);

	return 0;
}